package 剑指offer;

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<String> ans = new ArrayList<>();
    int n;
    int t;
    String s;
    public List<String> addOperators(String num, int target) {
        if(num.length() == 0) return ans;
        n = num.length();
        t = target;
        s = num;
        dfs(0,0,0,"");
        return ans;
    }
    void dfs(int index,long prev,long cur,String str){
        if(index == n){
            if(cur == t) ans.add(str);
            return;
        }
        for(int i = index;i<n;++i){
            if(i != index && s.charAt(index) == '0')break;
            long next = Long.parseLong(s.substring(index, i + 1));
            if(index == 0){
                dfs(i + 1,next,next,""+next);
            }else{
                dfs(i + 1,next,cur + next,str + "+" + next);
                dfs(i + 1,-next,cur - next,str + "-" + next);
                dfs(i + 1,prev * next, cur - prev + prev * next,str + "*" + next);
            }
        }
    }
}
